package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 1305. 两棵二叉搜索树中的所有元素
 *
 * @Author liw
 * @Date 2021/5/18 14:58
 * @Version 1.0
 */
public class GetAllElements {

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        find(root1, a);
        find(root2, b);
        return sort(a, b);
    }

    private List<Integer> sort(List<Integer> a, List<Integer> b) {
        int s1 = a.size();
        int s2 = b.size();
        List<Integer> list = new ArrayList<>(s1 + s2);
        int i = 0;
        int j = 0;
        while (i < s1 && j < s2) {
            if (a.get(i) > b.get(j)) {
                list.add(b.get(j++));
            } else {
                list.add(a.get(i++));
            }
        }
        while (i < s1) {
            list.add(a.get(i++));
        }

        while (j < s2) {
            list.add(b.get(j++));
        }
        return list;
    }

    private void find(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        find(node.left, list);
        list.add(node.val);
        find(node.right, list);
    }

}
